package graph;

import java.util.*;

public class CourseScheduleii210 {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] deg = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int begin = prerequisites[i][1];
            int end = prerequisites[i][0];
            Set<Integer> set = map.getOrDefault(begin, new HashSet<>());
            set.add(end);
            map.put(begin, set);
            deg[end]++;
        }
        int[] result = new int[numCourses];
        int index = 0;
        LinkedList<Integer> quene = new LinkedList<>();
        for (int i = 0; i < deg.length; i++) {
            if (deg[i] == 0) {
                quene.offer(i);
            }
        }

        while (quene.size() != 0) {
            int n = quene.poll();
            result[index++] = n;
            Set<Integer> set = map.get(n);
            if (set != null && !set.isEmpty()) {
                for (Integer i : set
                ) {
                    deg[i]--;
                    if (deg[i] == 0) {
                        quene.offer(i);
                    }
                }

            }
        }
        if (index != numCourses) {
            return new int[]{};
        } else {
            return result;
        }

    }
}
